package com.cet.algorithm.动态规划.最后一块石头的重量;

/**
 * @program: cet-practice
 * @description: 最后一块石头的重量
 * @author: 陈恩涛
 * @create: 2023-08-03 14:38
 **/
public class Lc1049 {

    public int lastStoneWeightII(int[] stones) {
        // bag problem

        // dp[j] a bag obtain max value within capacity of j

        // dp[0] = 0

        // dp[j] = max{dp[j], dp[j - weight[i]] + value[i]}

        int sum = 0;

        for(int i = 0; i < stones.length; i++){
            sum += stones[i];
        }

        int target = sum / 2;

        int[] dp = new int[target + 1];

        for(int i = 0; i < stones.length; i++){
            for(int j = target; j >= stones[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return sum - dp[target] - dp[target];
    }

    public static void main(String[] args) {

    }
}
